#ifndef ARRAY
#define ARRAY

#include <vector>
#include "allocator.h"
#include "../define.h"

#if defined(_DEBUG)
#   if defined(_IRR_WINDOWS_API_) && defined(_MSC_VER) && !defined (_WIN32_WCE)
#       if defined(WIN64) || defined(_WIN64) // using portable common solution for x64 configuration
#           include <crtdbg.h>
#           define DEBUG_BREAK_IF( _CONDITION_ ) if (_CONDITION_) {_CrtDbgBreak();}
#       else
#           define DEBUG_BREAK_IF( _CONDITION_ ) if (_CONDITION_) {_asm int 3}
#       endif
#   else
#       include "assert.h"
#       define DEBUG_BREAK_IF( _CONDITION_ ) assert( !(_CONDITION_) );
#   endif
#else
#   define DEBUG_BREAK_IF( _CONDITION_ )
#endif

namespace sleek
{
    namespace core
    {
        namespace math
        {
            template <class T, typename TAlloc = allocator<T> >
            class array
            {

                public:
                    array() : data(0), allocated(0), used(0), strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) { }
                    array(u32 start_count) : data(0), allocated(0), used(0), strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) { reallocate(start_count); }
                    array(const array<T, TAlloc>& other) : data(0) { *this = other; }
                    ~array() { clear(); }

                    inline void reallocate(u32 new_size)
                    {
                        T* old_data = data;
                        data = allocator.allocate(new_size); //new T[new_size];
                        allocated = new_size;
                        s32 end = used < new_size ? used : new_size;
                        for (s32 i=0; i<end; ++i) allocator.construct(&data[i], old_data[i]);
                        for (u32 j=0; j<used; ++j) allocator.destruct(&old_data[j]);
                        if (allocated < used) used = allocated;
                        allocator.deallocate(old_data); //delete [] old_data;
                    }
                    inline void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE ) { strategy = newStrategy; }
                    inline void push_back(const T& element) { insert(element, used); }
                    inline void push_front(const T& element) { insert(element); }
                    inline void insert(const T& element, u32 index=0)
                    {
                        DEBUG_BREAK_IF(index>used) // access violation
                        if (used + 1 > allocated)
                        {
                            const T e(element);
                            u32 newAlloc;
                            switch ( strategy )
                            {
                                case ALLOC_STRATEGY_DOUBLE:
                                    newAlloc = used + 1 + (allocated < 500 ?
                                    (allocated < 5 ? 5 : used) : used >> 2);
                                    break;
                                default:
                                case ALLOC_STRATEGY_SAFE: newAlloc = used + 1; break;
                            }
                            reallocate( newAlloc);
                            for (u32 i=used; i>index; --i)
                            {
                                if (i<used) allocator.destruct(&data[i]);
                                allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
                            }
                            if (used > index) allocator.destruct(&data[index]);
                            allocator.construct(&data[index], e); // data[index] = e;
                        }
                        else
                        {
                            if ( used > index )
                            {
                                allocator.construct(&data[used], data[used-1]);
                                for (u32 i=used-1; i>index; --i) data[i] = data[i-1];
                                data[index] = element;
                            }
                            else allocator.construct(&data[index], element);
                        }
                        is_sorted = false;
                        ++used;
                    }
                    inline void clear()
                    {
                        if(free_when_destroyed)
                        {
                            for (u32 i=0; i<used; ++i) allocator.destruct(&data[i]);
                            allocator.deallocate(data); // delete [] data;
                        }
                        data = 0; used = 0; allocated = 0;
                        is_sorted = true;
                    }
                    inline void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
                    {
                        clear();
                        data = newPointer;
                        allocated = size;
                        used = size;
                        is_sorted = _is_sorted;
                        free_when_destroyed=_free_when_destroyed;
                    }
                    inline void set_free_when_destroyed(bool f) { free_when_destroyed = f; }
                    inline void set_used(u32 usedNow){if (allocated < usedNow)reallocate(usedNow); used = usedNow; }
                    inline const array<T, TAlloc>& operator=(const array<T, TAlloc>& other)
                    {
                        if (this == &other) return *this;
                        strategy = other.strategy;

                        if (data) clear();
                        //if (allocated < other.allocated)
                        if (other.allocated == 0) data = 0;
                        else data = allocator.allocate(other.allocated); // new T[other.allocated];

                        used = other.used;
                        free_when_destroyed = true;
                        is_sorted = other.is_sorted;
                        allocated = other.allocated;

                        for (u32 i=0; i<other.used; ++i)  allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];
                        return *this;
                    }
                    inline bool operator == (const array<T, TAlloc>& other) const{ if (used != other.used) return false; for (u32 i=0; i<other.used; ++i) if (data[i] != other[i]) return false; return true; }
                    inline bool operator != (const array<T, TAlloc>& other) const { return !(*this==other); }
                    inline T& operator [](u32 index) { DEBUG_BREAK_IF(index>=used) return data[index]; }
                    inline const T& operator [](u32 index) const { DEBUG_BREAK_IF(index>=used) return data[index]; }
                    inline T& getLast() { DEBUG_BREAK_IF(!used) return data[used-1]; }
                    inline const T& getLast() const { DEBUG_BREAK_IF(!used) return data[used-1]; }
                    inline T* pointer() { return data; }
                    inline const T* const_pointer() const { return data; }
                    inline u32 size() const { return used; }
                    inline u32 allocated_size() const { return allocated; }
                    inline bool empty() const { return used == 0; }
                    inline void sort() { if (!is_sorted && used>1) heapsort(data, used); is_sorted = true;  }
                    inline s32 binary_search(const T& element) { sort(); return binary_search(element, 0, used-1); }
                    inline s32 binary_search(const T& element) const { if (is_sorted) return binary_search(element, 0, used-1); else return linear_search(element); }
                    inline s32 binary_search(const T& element, s32 left, s32 right) const
                    {
                        s32 m;
                        if (!used) return -1;

                        do
                        {
                            m = (left+right)>>1;
                            if (element < data[m]) right = m - 1;
                            else left = m + 1;
                        } while((element < data[m] || data[m] < element) && left<=right);

                        if (!(element < data[m]) && !(data[m] < element)) return m;
                        return -1;
                    }
                    inline s32 binary_search_multi(const T& element, s32 &last)
                    {
                        sort();
                        s32 index = binary_search(element, 0, used-1);
                        if ( index < 0 ) return index;
                        last = index;
                        while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )  index -= 1;
                        while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) ) last += 1;
                        return index;
                    }
                    inline s32 linear_search(const T& element) const
                    {
                        for (u32 i=0; i<used; ++i) if(element == data[i]) return (s32)i;
                        return -1;
                    }
                    inline s32 linear_reverse_search(const T& element) const
                    {
                        for (s32 i=used-1; i>=0; --i)  if(data[i] == element) return i;
                        return -1;
                    }
                    inline void erase(u32 index)
                    {
                        DEBUG_BREAK_IF(index>=used) // access violation
                        for (u32 i=index+1; i<used; ++i)
                        {
                            allocator.destruct(&data[i-1]);
                            allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
                        }
                        allocator.destruct(&data[used-1]);
                        --used;
                    }
                    inline void erase(u32 index, s32 count)
                    {
                        u32 i;
                        if (index>=used || count<1) return;
                        if (index+count>used) count = used-index;
                        for (i=index; i<index+count; ++i) allocator.destruct(&data[i]);
                        for (i=index+count; i<used; ++i)
                        {
                            if (i > index+count) allocator.destruct(&data[i-count]);
                            allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];
                            if (i >= used-count) allocator.destruct(&data[i]);
                        }
                        used -= count;
                    }
                    inline void set_sorted(bool _is_sorted) { is_sorted = _is_sorted; }
                    inline void swap(array<T, TAlloc>& other)
                    {
                        swap(data, other.data);
                        swap(allocated, other.allocated);
                        swap(used, other.used);
                        swap(allocator, other.allocator);	// memory is still released by the same allocator used for allocation
                        eAllocStrategy helper_strategy(strategy);	// can't use swap with bitfields
                        strategy = other.strategy;
                        other.strategy = helper_strategy;
                        bool helper_free_when_destroyed(free_when_destroyed);
                        free_when_destroyed = other.free_when_destroyed;
                        other.free_when_destroyed = helper_free_when_destroyed;
                        bool helper_is_sorted(is_sorted);
                        is_sorted = other.is_sorted;
                        other.is_sorted = helper_is_sorted;
                    }
                protected:
                    template <class T1, class T2>
                    inline void swap(T1& a, T2& b) { T1 c(a);  a = b;  b = c; }
                private:
                    T* data;
                    u32 allocated;
                    u32 used;
                    TAlloc allocator;
                    eAllocStrategy strategy:4;
                    bool free_when_destroyed:1;
                    bool is_sorted:1;
            };
        }
    }
}

#endif
